package com.example.demo.suanfa;

import org.junit.Test;
import java.util.HashMap;
import java.util.HashSet;

/**
 *
 */
public class Questions {

    // 自己写的烂代码
    public int[] generateArray(int maxNumberKinds, int range, int k, int m) {

        int oneKindNumber = randomNumber(range);

        int numberKinds = (int) (Math.random() * maxNumberKinds) + 2;

        int[] arr = new int[k + (numberKinds - 1) * m];
        int index = 0;
        for (; index < k; index++) {
            arr[index] = oneKindNumber;
        }

        HashSet<Integer> dif = new HashSet<>();
        dif.add(oneKindNumber);
        numberKinds--;
        for (int i = 0; i < numberKinds; i++) {
            int mRandomNumber = randomNumber(range);
            if (!dif.contains(mRandomNumber)) {
                for (int j = 0; j < m; j++) {
                    arr[index] = mRandomNumber;
                    index++;
                }
            }
        }
        return null;
    }
    // [-rang,rang]
    private int randomNumber(int range) {
        return ((int)(Math.random() * range) + 1)-((int)(Math.random() * range) + 1);
    }

    public int[] generateArrayBetter(int maxNumberKinds, int range, int k, int m) {
        k = (Math.random() < 0.5) ? k : (int) ((Math.random() * (m - 1)) + 1);
        int oneKindNumber = randomNumber(range);
        int numberKinds = (int) (Math.random() * maxNumberKinds) + 2;
        int[] arr = new int[k + (numberKinds - 1) * m];
        int index = 0;
        for (; index < k; index++) {
            arr[index] = oneKindNumber;
        }

        HashSet<Integer> set = new HashSet<>();
        set.add(oneKindNumber);
        numberKinds--;

        while (numberKinds > 0){
            int curNum = 0;
            do {
                curNum = randomNumber(range);
            } while (set.contains(curNum));
            set.add(curNum);
            numberKinds--;
            for (int i = 0; i < m; i++) {
                arr[index++] = curNum;
            }
        }
        // 打乱顺序
        for (int i = 0; i < arr.length; i++) {
            int j = (int) (Math.random() * arr.length);
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        return arr;
    }

    /**
     * 对数器
     * 校验算法正确性
     */
    @Test
    public void test05_validate() {
        int maxNumberKinds = 5;
        int range = 200;
        int testTimes = 10_000;
        int max = 9;
        System.out.println("测试开始");
        for (int i = 0; i < testTimes; i++) {
            int a = (int) (Math.random() * max) + 1;// 随机生成了1 到 9
            int b = (int) (Math.random() * max) + 1;// 随机生成了1 到 9
            int k = Math.min(a, b);
            int m = Math.max(a, b);
            if (k == m) {
                m++;
            }

            int[] ints = generateArrayBetter(maxNumberKinds, range, k, m);
            int i1 = test05_2(ints, k, m);
            int i2 = test04(ints, k, m);
            if (i1 != i2){
//                System.out.println("测试出错");
                System.out.println(i1);
                System.out.println(i2);
                System.out.println("----------");
            }
        }
        System.out.println("测试结束");
    }

    /**
     * 无序数组，可以正负
     * 相邻数 不相等
     * 小于1亿数据
     * 求局部最小值 ?
     * 要求：
     * ... pre > mid < post...  mid 为局部最小值
     * pre < post .... pre 为局部最小值
     * ...pre > post post为局部最小值
     */
    @Test
    public void testMIn() {
        // 返回局部最小值的 index
        int ret = -1;
        int[] arr = {1, 0, 1};
        // 判断边界条件
        if (arr.length == 0) {
            return;
        }
        if (arr.length == 1 || arr[0] < arr[1]) {
            ret = 0;
            return;
        }
        if (arr[arr.length - 1] < arr[arr.length - 2]) {
            ret = arr.length - 1;
            return;
        }

        //////  通过 二分查找法，找到 局部最小值
        //  到此步， 通过判断可知 头尾不是局部最小值，
        //  左向右为降趋势
        //  右向左为也为降趋势 ，哪中间一定存在一个最小值
        int L = 1;
        int R = arr.length - 2;
        int mid = 0;
        while (L <= R) {
//            int mid = L + ((R - L) >> 1);
            mid = (L + R) / 2;
            if (arr[mid] > arr[mid - 1]) {
                R = mid - 1;
            } else if (arr[mid] > arr[mid + 1]) {
                L = mid + 1;
            } else {
                ret = mid;
                break;
            }
        }
        System.out.println(ret);

    }


    /**
     * 异或运算 运用
     * 一组数，有一个数出现奇数次，其余都出现偶数次。找出这个奇数次数
     */
    @Test
    public void test01() {
        int[] arr = {};
        int a = 0;
        for (int i = 0; i < arr.length; i++) {
            a = a ^ arr[i];
        }
        System.out.println(a);
    }


    /**
     * 异或运算
     * 找出 一个int类型的数  最右侧byte位的1
     */
    @Test
    public void test02() {
        int a = 23234;
        int x = a & (~a + 1);
        int y = a & (-a);
        System.out.println(x);
    }

    /**
     * 异或运算
     * 找出 一个数组内有两种数，出现了奇数次，其他都出现了偶数次，找到这两种数。
     */
    @Test
    public void test03() {
        int[] arr = {};
        int eor = 0;
        for (int i = 0; i < arr.length; i++) {
            eor ^= arr[i];
        }
        // leftEor 为最右侧不为0的数
        int leftEor = eor ^ (-eor);
        for (int i = 0; i < arr.length; i++) {
            if ((leftEor & arr[i]) == 0) {
                leftEor ^= arr[i];
            }
        }
        int a = leftEor ^ eor;
        int b = leftEor;
    }

    /**
     * 异或运算
     * 一个数组中有一种数出现了K次，其他数都出现了M次。
     * M>1   K<M
     * 找到出现K次的数
     * 要求：额外空间复杂度O（1），时间复杂度 O（N）
     */
    public int test04(int[] arr, int k, int m) {
        int[] target = new int[32];
        for (int i = 0; i < arr.length; i++) {
            int inn = arr[i];
            for (int j = 0; j < target.length; j++) {
                target[j] += (inn >> j) & 1;
            }
        }

        int ans = 0;
        for (int i = 0; i < target.length; i++) {
            if (target[i] % m == 0) {
                continue;
            }
            if (target[i] % m == k){
                ans |= (1 << i);
            }else {
                return -1;
            }
        }
        if (ans == 0){
            int count = 0;
            for (int i = 0; i < arr.length; i++) {
                if (arr[i] ==0){
                    count++;
                }
            }
            return count == k ? ans : -1;
        }
        return ans;
    }


    /**
     * 异或运算
     * 一个数组中有一种数出现了K次，其他数都出现了M次。
     * M>1   K<M
     * 找到出现K次的数
     * 要求：额外空间复杂度O（1），时间复杂度 O（N）
     * 如果使用 hashMap解决
     */
    @Test
    public void test05() {
        int k = 2;
        int M = 3;
        int[] arr = {1, 1, 3, 3, 3, 4, 4, 4, 5, 5, 5};
        int i = test05_2(arr, k, M);
        int i1 = test04(arr, k, M);
        System.out.println(i);
        System.out.println(i1);
    }

    public int test05_2(int[] arr, int k, int m) {
        HashMap<Integer, Integer> hashMap = new HashMap();
        for (int i = 0; i < arr.length; i++) {
            if (hashMap.containsKey(arr[i])) {
                hashMap.put(arr[i], hashMap.get(arr[i]) + 1);
            } else {
                hashMap.put(arr[i], 1);
            }
        }
        for (int c : hashMap.keySet()) {
            if (hashMap.get(c) == k) {
                return c;
            }
        }
        return -1;
    }


}
